class Solution {
public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& rooti, int begin, int end) {
        if (begin > end)
            return nullptr;

        TreeNode* root = new TreeNode(postorder[rooti--]);


        int temp = begin;
        while (temp <= end)
        {
            if (postorder[rooti + 1] == inorder[temp])
                break;
            else
                temp++;
        }

        root->right = _buildTree(inorder, postorder, rooti, temp + 1, end);
        root->left = _buildTree(inorder, postorder, rooti, begin, temp - 1);


        return root;


    }


    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = inorder.size() - 1;
        return _buildTree(inorder, postorder, i, 0, inorder.size() - 1);
    }
};
